import data.structure.ListNode;
/*给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。



示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
*/
public class test35 {
    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(4);
        head1.next.next = new ListNode(5);
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(3);
        head2.next.next = new ListNode(4);
        ListNode head3 = new ListNode(2);
        head3.next = new ListNode(6);
        ListNode[] lists = new ListNode[]{head1, head2, head3};
        ListNode result = mergeKLists(lists);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
        System.out.println();

        // 测试包含空链表的情况
        ListNode head4 = null; // []
        ListNode head5 = new ListNode(-1);
        head5.next = new ListNode(5);
        head5.next.next = new ListNode(11); // [-1, 5, 11]
        ListNode head6 = null; // []
        ListNode head7 = new ListNode(6);
        head7.next = new ListNode(10); // [6, 10]
        ListNode[] lists2 = new ListNode[]{head4, head5, head6, head7};
        ListNode result2 = mergeKLists(lists2);
        while (result2 != null) {
            System.out.print(result2.val + " ");
            result2 = result2.next;
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        int subLength = lists.length;
        if (subLength == 0)
            return null;

        // 处理空链表
        while (subLength > 1) {
            int k = (subLength + 1) / 2;
            for (int i = 0; i < subLength / 2; i++) {
                lists[i] = merged(lists[i], (i + k < subLength) ? lists[i + k] : null);
            }
            subLength = k;
        }
        return lists[0];
    }

    private static ListNode merged(ListNode head1, ListNode head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;

        ListNode result = new ListNode(0);
        ListNode prev = result;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                prev.next = head1;
                prev = prev.next;
                head1 = head1.next;
            } else {
                prev.next = head2;
                prev = prev.next;
                head2 = head2.next;
            }
        }
        if (head1 != null) {
            prev.next = head1;
        } else {
            prev.next = head2;
        }
        return result.next;
    }
}
